﻿using System.Collections.Generic;
using Xunit;
using Xunit.Abstractions;

namespace 初级算法.其他
{
    public class 回文链表   
    {
        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }
        }
        public class Solution
        {
            /// <summary>
            /// 将链表中的数据存到集合（数组）中。双指针判断 2021-7-13
            /// 执行用时：248 ms, 在所有 C# 提交中击败了95.57%的用户
            /// 内存消耗：47.1 MB, 在所有 C# 提交中击败67.00%的用户
            /// </summary>
            /// <param name="head"></param>
            /// <returns></returns>
            public bool IsPalindrome(ListNode head)
            {
                List<int>  nums = new List<int>() ;
                while (head != null)
                {
                    nums.Add(head.val);
                    head = head.next;
                }
                int first = 0, last = nums.Count - 1;
                while (first < last)
                {
                    if (nums[first] != nums[last]) return false;

                    first++;
                    last--;
                }

                return true;
            }

        }
        ITestOutputHelper output;

        public 回文链表(ITestOutputHelper output)
        {
            this.output = output;
        }

        [Fact]
        public void Test1()
        {

            Solution S = new Solution();
            ListNode n;
            bool r;
            //n = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
            //r = S.RemoveNthFromEnd(n,2);
            //Print(r);

            n = new ListNode(1, new ListNode(2));
            r = S.IsPalindrome(n);
            Print(r);


            output.WriteLine("");

            n = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))));
            r = S.IsPalindrome(n);
            Print(r);
        }


        private void Print(bool n)
        {
            output.WriteLine("" + n);
        }
    }
}
